package com.example.algorithm.model;

/**
 * @auth Administrator
 * @create @2025/4/15@21:10
 * @decription
 **/







public class MyLinkedList {

    private static class Node {
        int val;
        Node pre,next;
        Node( Node pre ,int val ,Node next){
            this.val = val;
            this.pre = pre;
            this.next = next;
        }

    }


    private  Node first=null;

    private Node last = null;

    private  int  size=0;

    public  MyLinkedList(){

    }

    /**
     * 是否为有效位置
     * @param index
     * @return
     */
    public  boolean isElementIndex(int index){
        return index>=0&&index<size;
    }


    /**
     *  根据索引获取节点
     * @param index
     * @return
     */
    public Node getNode(int index){
        if(!isElementIndex(index)){
            return  null;
        }
        if(index<size>>1){
            Node x = first;
            for(int i=0;i<index;i++){
                x= x.next;
            }
            return x;
        }else{
            Node x = last;
            for(int i=size-1;i>index;i--){
                x= x.pre;
            }
            return x;
        }
    }

    /**
     *  头插法
      * @param val
     */
    public  void addAtHead(int val){
     Node newNode = new Node(null,val,first);
     if(first!=null){
         first.pre=newNode;
     }
     first=newNode;
     if(last==null){
         last=first;
     }
     size++;
    }

    /**
     * 尾插法
     * @param val
     */
    public  void  addAtTail(int val){
        Node newNode = new Node(last,val,null);
        if(last!=null){
            last.next=newNode;
        }
        last = newNode;
        if(first==null){
            first = last;
        }
        size++;

    }

    /**
     * 按照位置添加节点
     * @param index
     * @param val
     */
    public  void addAtIndex(int index,int val){
        if(index>size){
            return;
        }
        if(index==size){
            addAtTail(val);
        }else if(index<=0){
            addAtHead(val);
        }else{
            Node node = getNode(index);
            Node newNode = new Node(node.pre,val,node.next);
            if(node.pre!=null){
                node.pre.next=newNode;
            }
            node.pre=newNode;
            size++;
        }

    }

    /**
     * 按照位置删除节点
     * @param index
     */
    public  void deleteAtIndex(int index){
      if(!isElementIndex(index)){
          return;
      }
        Node node = getNode(index);
        if(index==0){
            first = node.next;
            if(size>1){
                node.next.pre=null;
            }
            node.next=null;
        }else if(index == size-1){
            last = node.pre;
            if(size>1){
                node.pre.next=null;
            }
           node.pre=null;
        }else{
            node.pre.next=node.next;
            node.next.pre=node.pre;
        }
        size--;

    }


}
